package leetcode100;

import java.util.HashMap;
import java.util.Map;

public class lc051 {
    public static void main(String[] args) {

    }

    /**
     * 前序遍历: 根左右, 可以从左到右获取一个个根节点,
     * 如果把每一个根的左右子树都找出来, 连上去就是整棵树
     * 而左右子树的建立可以根据 中序遍历, 找出根的位置,左边都是左子树, 右边都是右子树
     * @param preorder
     * @param inorder
     * @return
     */

    private Map<Integer,Integer> value2IndexMap = new HashMap<>();

    private int preIndex;


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < preorder.length; i++) {
            this.value2IndexMap.put(inorder[i], i);
        }
        TreeNode root = this.build(preorder, 0,preorder.length-1);
        return root;
    }

    private TreeNode build(int[] preorder, int start,int end) {
        if(start>end) {
            return null;
        }
        int rootValue = preorder[this.preIndex];
        TreeNode root = new TreeNode(rootValue);
        this.preIndex++;
        int rootIndexInorder = this.value2IndexMap.get(rootValue);
        TreeNode left = build(preorder, start,rootIndexInorder-1);
        TreeNode right = build(preorder,rootIndexInorder+1,end);
        root.left=left;
        root.right = right;

        return root;
    }

}
